#include  <iostream>
using  namespace  std;

#define  MVNum  100                                                        //最大顶点数

//-------------图的邻接表---------------------
struct  ArcNode{                                                //边结点  
	int  adjvex;                                                  //该边所指向的顶点的位置  
	ArcNode  *nextarc;                                    //指向下一条边的指针  
};  

struct  VNode{  
	char  data;                                                //顶点信息
	ArcNode  *firstarc;                                        //指向第一条依附该顶点的边的指针  
};                                                            //AdjList表示邻接表类型  

struct  ALGraph{
	VNode  vertices[MVNum];                                          //邻接表  
	int  vexnum,  arcnum;                                            //图的当前顶点数和边数  
};

bool  visited[MVNum];                                                      //访问标志数组，其初值为"false"  

int  LocateVex(ALGraph  G  ,  char  v){
	//确定点v在G中的位置
	for(int  i  =  0;  i  <  G.vexnum;  ++i)
		if(G.vertices[i].data  ==  v)
			return  i;
	return  -1;
}//LocateVex

void  CreateUDG(ALGraph  &G){  
	//采用邻接表表示法，创建无向图G
	int  i  ,  k;
	
	//请输入总顶点数，总边数，以空格隔开
	cin  >>  G.vexnum  >>  G.arcnum;                                //输入总顶点数，总边数  
	cout  <<  endl;
	
	//输入点的名称，如a
	
	for(i  =  0;  i  <  G.vexnum;  ++i){                            //输入各点，构造表头结点表
		//请输入各个点的名称
		cin  >>  G.vertices[i].data;                              //输入顶点值  
		G.vertices[i].firstarc=NULL;                        //初始化表头结点的指针域为NULL  
	}//for
	cout  <<  endl;
	
	//输入边依附的顶点，如a  b
	
	for(k  =  0;  k  <  G.arcnum;++k){                                //输入各边，构造邻接表
		char  v1  ,  v2;
		int  i  ,  j;
		//请输入各个边依附的顶点
		cin  >>  v1  >>  v2;                                                  //输入一条边依附的两个顶点
		i  =  LocateVex(G,  v1);    j  =  LocateVex(G,  v2);
		//确定v1和v2在G中位置，即顶点在G.vertices中的序号  
		
		ArcNode  *p1=new  ArcNode;                                      //生成一个新的边结点*p1  
		p1->adjvex=j;                                                      //邻接点序号为j  
		p1->nextarc=  G.vertices[i].firstarc;    G.vertices[i].firstarc=p1;    
		//将新结点*p1插入顶点vi的边表头部
		
		ArcNode  *p2=new  ArcNode;                                //生成另一个对称的新的边结点*p2  
		p2->adjvex=i;                                                    //邻接点序号为i  
		p2->nextarc=  G.vertices[j].firstarc;    G.vertices[j].firstarc=p2;    
		//将新结点*p2插入顶点vj的边表头部  
	}//for  
}//CreateUDG

void DFS(ALGraph g,int i){
	cout << g.vertices[i].data;
	visited[i] = 1;
	ArcNode *p = g.vertices[i].firstarc;
	
	while(p){
		if(visited[p->adjvex] == 0)
			DFS(g,p->adjvex);
		p=p->nextarc;
	}
}

int  main(){
	//采用邻接表表示图的深度优先搜索遍历
	ALGraph  G;         //AL 邻接表
	CreateUDG(G);
	cout  <<  endl;
	//请输入遍历连通图的起始点
	char  c;
	cin  >>  c;
	
	int  i;
	for(i  =  0  ;  i  <  G.vexnum  ;  ++i){
		if(c  ==  G.vertices[i].data)
			break;
	}
	cout  <<  endl;
	while(i  >=  G.vexnum){
		cout  <<  "该点不存在，请重新输入！"  <<  endl;
		//请输入遍历连通图的起始点
		cin  >>  c;
		for(i  =  0  ;  i  <  G.vexnum  ;  ++i){
			if(c  ==  G.vertices[i].data)
				break;
		}
	}
	
	//深度优先搜索遍历图结果
	DFS(G  ,  i);
	
	cout  <<endl;
	return  0;
}//main
